package sort.swap;

import java.util.Arrays;

public class QuickTwo {

    //快排1，获取中枢
    public static int getqs1Mid(int[] array,int left,int right) {
        //初始记录中枢为数组第一个元素值
        int index = array[left];
        //判断下标，初始轮，右边寻找
        while(left < right) {
            //从右开始，第一个比中枢小的元素，若不存在，数组有序退出条件为left==right
            while(array[right] >= index && left < right) {
                right--;
            }
            //交换，左边寻找开始
            array[left] = array[right];
            //从左开始，第一个比中枢大的元素，若不存在，数组有序退出条件为left==right
            while(array[left] <= index && left < right) {
                left++;
            }
            //交换，次轮开始
            array[right] = array[left];
        }
        //赋予中枢值
        array[left] = index;
        //返回排好的中枢下标
        index = left;
        return index;
    }

    public static int[] quickSort1(int[] array,int left,int right) {
        int index = 0;
        //判断左右下标
        if(left < right) {
            //获取中枢下标
            index = getqs1Mid(array, left, right);
            //中枢左边递归，直至left==right
            quickSort1(array, left, index-1);
            //中枢右边递归，直至left==right
            quickSort2(array, index+1, right);
        }
        return array;
    }

    //快排2，左右交换
    public static int[] quickSort2(int[] array,int left,int right) {
        //记录左移动下标
        int i = left;
        //记录右移动下标
        int j = right;
        int temp = 0;
        int pivot;
        //记录数组中间元素的值
        if((array[(left+right)/2]-array[left])*(array[left]-array[right])>=0) {
            pivot = array[left];
        } else if((array[left]-array[right])*(array[right]-array[(left+right)/2])>=0){
            pivot = array[right];
        } else {
            pivot = array[(left+right)/2];
        }

        //下标交替
        while(i<=j) {
            //寻找左下标，左边第一个大于pivot的元素，等于时保底元素不会越过中值
            while(pivot > array[i]) {
                i++;
            }
            //寻找右下标，右边第一个小于pivot的元素，等于时保底元素不会越过中值
            while(pivot < array[j]) {
                j--;
            }
            //交换一次，并使i，j覆盖整个数组
            if(i<=j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
            //左快排
            if (right > i) {
                quickSort2(array, i, right);
            }
            //右快排
            if (left < j) {
                quickSort2(array, left, j);
            }
        }

        return array;
    }

    public static void main(String[] args) {
        int[] array = {2,4,2,1,3,5,7,10,5,122,56,12,5};
        //{3,6,2,8,9,10,345,1,3};//{9,1,3,4};//

        array = quickSort1(array, 0, array.length-1);
        //array = quickSort2(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
}